package com.south.base.test.arithmetic;

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

/**
 * @author Administrator
 * @date 2020/8/31 9:31
 */
public class Rooms {
    /**
     * 钥匙和房间
     * 有 N 个房间，开始时你位于 0 号房间。
     * 每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。
     * 在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，
     * 其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。
     * 最初，除 0 号房间外的其余所有房间都被锁住。
     * 你可以自由地在房间之间来回走动。
     * 如果能进入每个房间返回 true，否则返回 false。
     */
    @Test
    public void canVisitAllRooms() {
        Assert.assertTrue(canVisitAllRooms(Arrays.asList(Arrays.asList(1), Arrays.asList(2), Arrays.asList(3), new ArrayList<>())));
        Assert.assertFalse(canVisitAllRooms(Arrays.asList(Arrays.asList(1, 3), Arrays.asList(3, 0, 1), Arrays.asList(2), Arrays.asList(0))));
    }

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        if (rooms.size() <= 1) {
            return true;
        }
        boolean[] res = new boolean[rooms.size()];
        res[0] = true;
        Queue<List<Integer>> keys = new LinkedList<>();
        keys.add(rooms.get(0));
        while (!keys.isEmpty()) {
            List<Integer> key = keys.poll();
            if (key == null) {
                break;
            }
            for (Integer i : key) {
                if (!res[i]) {
                    keys.add(rooms.get(i));
                    res[i] = true;
                }
            }
        }
        boolean f = true;
        for (boolean r : res) {
            f &= r;
        }
        return f;
    }
}
